In order to make semiconductor memory devices capable of high-density recording, error correction codes for digital data are under development. The error correction codes can be roughly divided into algebraic codes and codes prepared by probability-based iterative calculations. Regarding Low Density Parity Check codes (hereinafter referred to as “LDPC codes”) which belong to the latter category, excellent performance close to the Shannon limit has been reported.
The LDPC codes are linear codes defined by a very sparse parity check matrix, i.e., a parity check matrix containing a small number of non-zero elements, and can be represented by a Tanner graph. Decoding involves exchanging results locally inferred by row processing and column processing between a bit node corresponding to each bit of code words connected on the Tanner graph and a check node corresponding to each parity check equation. Then, error correction is performed through repeated cycles of iterative processing which includes the row processing and column processing.
LDPC encoded data can be decoded by parallel processing on a relatively small circuit scale using the Sum-Product algorithm. Decoding by means of the Sum-Product algorithm can be roughly divided into batch decoding whereby row processing and column processing are performed in batches and serial decoding whereby row processing and column processing are performed serially with respect to each row index. The serial decoding is known to be faster in convergence speed and lower in memory consumption than the batch decoding.
Row operations for performing processing operations in a row direction of the parity check matrix in the Sum-Product algorithm involve nonlinear function calculations and thus particularly large amounts of operations, and therefore use the Min-Sum algorithm, which determines row operation data for each “1” element in each row of the parity check matrix by finding a minimum value among column operation data corresponding to the other “1” elements excluding the given element.